package com.datastructure.doublepointer;

/**
 * @author: 临晖
 * @date: 2023/10/18
 * @description:
 */


import sun.util.resources.cldr.ru.CalendarData_ru_UA;

import javax.print.attribute.standard.MediaSizeName;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.function.LongFunction;

/**
 * 双指针练习
 */
public class Solution {

    /**
     * 移除元素
     * <p>
     * 给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
     * 不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
     * 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
     *
     * @param nums
     * @param val
     * @return
     */
    public static int removeElement(int[] nums, int val) {
        int fastIndex = 0;
        int slowIndex = 0;

        for (; fastIndex < nums.length; fastIndex++) {
            if (nums[fastIndex] != val) {
                nums[slowIndex] = nums[fastIndex];
                slowIndex++;
            }
        }

        return slowIndex;

    }


    /**
     * 删除有序数组中的重复项
     * <p>
     * 给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。
     * 考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：
     * 更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
     * 返回 k
     *
     * @param nums
     * @return
     */
    public static int removeDuplicates(int[] nums) {
        int fastIndex = 1;
        int slowIndex = 0;

        for (; fastIndex < nums.length; fastIndex++) {
            if (nums[fastIndex] != nums[slowIndex]) {
                slowIndex++;
                nums[slowIndex] = nums[fastIndex];
            }
        }

        return slowIndex + 1;

    }


    /**
     * 移动零
     * <p>
     * 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
     * 请注意 ，必须在不复制数组的情况下原地对数组进行操作
     *
     * @param nums
     */
    public void moveZeroes(int[] nums) {
        //思路一
        //int fastIndex = 0;
        //int slowIndex = 0;
        //for (; fastIndex < nums.length; fastIndex++) {
        //    if (nums[fastIndex] != 0) {
        //        nums[slowIndex] = nums[fastIndex];
        //        slowIndex++;
        //    }
        //}
        //
        //for (int i = slowIndex; i < fastIndex; i++) {
        //    nums[i] = 0;
        //}

        //思路二
        int fastIndex = 0;
        int slowIndex = 0;
        for (; fastIndex < nums.length; fastIndex++) {
            if (nums[fastIndex] != 0) {
                int temp = nums[fastIndex];
                nums[fastIndex] = nums[slowIndex];
                nums[slowIndex] = temp;
                slowIndex++;
            }
        }

    }


    /**
     * 比较含有退格的字符串
     * <p>
     * 给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。
     * 注意：如果对空文本输入退格字符，文本继续为空。
     *
     * @param s
     * @param t
     * @return
     */
    public static boolean backspaceCompare(String s, String t) {
        int lenS = s.length();
        int lenT = t.length();

        int indexS = lenS - 1;
        int indexT = lenT - 1;
        //记录#的个数
        int skipS = 0;
        int skipT = 0;

        while (indexS >= 0 && indexT >= 0) {

            while (indexS >= 0) {

                if (s.charAt(indexS) == '#') {
                    skipS++;
                    indexS--;
                } else if (skipS > 0 && s.charAt(indexS) != '#') {
                    skipS--;
                    indexS--;
                } else {
                    break;
                }

            }

            while (indexT >= 0) {
                if (t.charAt(indexT) == '#') {
                    skipT++;
                    indexT--;
                } else if (skipT > 0 && t.charAt(indexT) != '#') {
                    skipT--;
                    indexT--;
                } else {
                    break;
                }
            }

            if (indexS >= 0 && indexT >= 0) {
                if (s.charAt(indexS) != t.charAt(indexT)) {
                    return false;
                }
            } else {
                if (indexS < 0 && indexT < 0) {
                    break;
                } else {
                    return false;
                }
            }

            indexT--;
            indexS--;

        }


        return true;
    }


    /**
     * 有序数组的平方
     * <p>
     * 给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
     *
     * @param nums
     * @return
     */
    public int[] sortedSquares(int[] nums) {
        int size = nums.length;
        int left = 0;
        int right = size - 1;

        int[] newNums = new int[size];

        while (left <= right) {
            if (nums[left] + nums[right] < 0) {
                newNums[--size] = nums[left] * nums[left];
                left++;
            } else {
                newNums[--size] = nums[right] * nums[right];
                right--;
            }
        }
        return newNums;
    }


    /**
     * 反转字符串
     * <p>
     * <p>
     * 编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
     * 不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
     *
     * @param s
     */
    public static void reverseString(char[] s, int left, int right) {

        while (left <= right) {
            char ch = s[left];
            s[left] = s[right];
            s[right] = ch;

            left++;
            right--;
        }
    }


    /**
     * 给你一个字符串 s ，请你反转字符串中 单词 的顺序。
     * 单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。
     * 返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。
     * 注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。
     *
     * @param s
     * @return
     */
    public static String reverseWords(String s) {
        char[] ans = s.toCharArray();
        //去除多余空格
        //判断首部是否有空格
        //判断尾部是否有空格
        int fastIndex = 0;
        int slowIndex = 0;
        for (; fastIndex < ans.length; fastIndex++) {
            if ((ans[fastIndex] != ' ') || (slowIndex > 0 && ans[fastIndex] == ' ' && ans[slowIndex - 1] != ' ')) {
                ans[slowIndex++] = ans[fastIndex];
            }
        }

        if (ans[fastIndex - 1] == ' ') {
            fastIndex--;
        }

        char[] newAns = Arrays.copyOf(ans, fastIndex);
        //反转整体
        reverseString(newAns, 0, newAns.length - 1);
        //反转单个单词
        int worldIndex = 0;
        for (int i = 0; i <= newAns.length; i++) {
            if (newAns[i] == ' ' || i == newAns.length) {
                reverseString(newAns, worldIndex, i - 1);
                worldIndex = i + 1;
            }
        }

        return new String(newAns);
    }


    /**
     * 反转链表
     * <p>
     * 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
     *
     * @param head
     * @return
     */
    public ListNode reverseList(ListNode head) {
        //思路一：改变方向
        //ListNode curr = null;
        //while (head != null) {
        //    ListNode temp = head;
        //    head = head.next;
        //    temp.next = curr;
        //    curr = temp;
        //}
        //
        //return curr;

        //思路二：递归

        return reverse(head, null);
    }

    public ListNode reverse(ListNode curr, ListNode pre) {
        if (curr == null) {
            return pre;
        }

        ListNode temp = curr.next;
        curr.next = pre;
        pre = temp;

        return reverse(temp, pre);
    }


    /**
     *
     * 删除链表的倒数第 N 个结点
     *
     * 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
     *
     * @param head
     * @param n
     * @return
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode node = new ListNode();
        node.next = head;
        ListNode curr = node;
        ListNode del = node;
        int count = 0;
        while (curr != null) {
            curr = curr.next;
            if (count <= n + 1) {
                count++;
            } else {
                del = del.next;
            }
        }

        del.next = del.next.next;
        return node.next;
    }


    /**
     * 面试题 02.07. 链表相交
     *
     * 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
     * 图示两个链表在节点 c1 开始相交
     * 题目数据 保证 整个链式结构中不存在环。
     * 注意，函数返回结果后，链表必须 保持其原始结构 。
     *
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {

        int countA = 0;
        int countB = 0;

        ListNode currA = headA;
        ListNode currB = headB;

        while (currA != null) {
            currA = currA.next;
            countA++;
        }

        while (currB != null) {
            currB = currB.next;
            countB++;
        }

        currA = headA;
        currB = headB;

        if (countA > countB) {
            int count = countA - countB;

            for (int i = 0; i < count; i++) {
                currA = currA.next;
            }

        } else {
            int count = countB - countA;
            for (int i = 0; i < count; i++) {
                currB = currB.next;
            }
        }

        while (currA != null) {
            if (currA == currB) {
                return currA;
            }
            currA = currA.next;
            currB = currB.next;
        }

        return null;
    }


    /**
     *环形链表 II
     *
     *给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
     * 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接
     * 到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
     *
     * @param head
     * @return
     */
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        //路径x
        ListNode curr = head;

        while (fast != null) {
            if (fast.next == null) {
                return null;
            }
            fast = fast.next.next;
            slow = slow.next;

            if (fast == slow) {     //肯定有环
                while (true) {
                    if (slow == curr) {
                        return curr;
                    }
                    slow = slow.next;
                    curr = curr.next;
                }
            }
        }

        return null;
    }


    /**
     *  三数之和
     *
     *
     * 给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
     * 你返回所有和为 0 且不重复的三元组。
     * 注意：答案中不可以包含重复的三元组。
     *
     * @param nums
     * @return
     */
    public List<List<Integer>> threeSum(int[] nums) {
        //先排序
        Arrays.sort(nums);
        ArrayList<List<Integer>> ans = new ArrayList<>();

       for (int i = 0; i < nums.length; i++) {
           if (nums[i] > 0 ) {
               break;
           }

           if (i > 0 && nums[i] == nums[i - 1]) {
               continue;
           }

           int left = i + 1;
           int right = nums.length - 1;

           while (left < right) {
               if (nums[i] + nums[left] + nums[right] > 0) {
                   right--;
               } else if (nums[i] + nums[left] + nums[right] < 0) {
                   left++;
               } else {
                   ans.add(Arrays.asList(nums[i], nums[left], nums[right]));
                   while (left < right && nums[left] == nums[left + 1]) {
                       left++;
                   }

                   while (left < right &&nums[right] == nums[right - 1]) {
                       right--;
                   }

                   left++;
                   right--;
               }
           }
       }
        return ans;


    }


    /**
     * 四数之和
     *
     *
     * 给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：
     * 0 <= a, b, c, d < n
     * a、b、c 和 d 互不相同
     * nums[a] + nums[b] + nums[c] + nums[d] == target
     * 你可以按 任意顺序 返回答案 。
     *
     * @param nums
     * @param target
     * @return
     */
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        ArrayList<List<Integer>> ans = new ArrayList<>();

        for (int i = 0; i  < nums.length; i++) {
            if (nums[i] > target && (target > 0 || nums[i] > 0)) {
                break;
            }

            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }

            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] > target &&  (target > 0 || nums[i] + nums[j] > 0)) {
                    break;
                }

                if (j > i + 1 && nums[j] == nums[j - 1]) {
                    continue;
                }

                int left = j + 1;
                int right = nums.length - 1;

                while (left < right) {
                    int sum = nums[i] + nums[j] + nums[left] + nums[right];
                    if (sum > target) {
                        right--;
                    } else if (sum < target){
                        left++;
                    } else {
                        ans.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));

                        while (left < right && nums[left] == nums[left + 1]) {
                            left++;
                        }

                        while (left < right && nums[right] == nums[right - 1]) {
                            right--;
                        }

                        left++;
                        right--;
                    }
                }
            }
        }

        return ans;

    }




    public static void main(String[] args) {
        
    }




}

